!> author: 左志华
!> date: 2022-06-07
!> Variable-length array structure
!> linear array vector data structure
!> 可变长度数组结构体定义:
!> 线性数组向量数据结构
!> @todo 视情况，待算法成型，考虑优化，即暂不优化
module list_type_m

    implicit none
    private

    public :: list_t, list_t_init, list_t_push, list_t_merge

    !> 列表
    !> list
    type list_t
        integer, allocatable :: items(:)    !! list items
                                            !! 表元素
        integer :: log                      !! list length
                                            !! 表元素个数
    contains
        procedure, private :: expand => list_t_expand
    end type list_t

contains

    !> init length
    !> 初始化长度
    elemental subroutine list_t_init(self, capacity)
        type(list_t), intent(inout) :: self     !! list
                                                !! 表
        integer, intent(in) :: capacity         !! list capacity
                                                !! 向量长度

        if (.not. allocated(self%items)) then
            allocate (self%items(capacity))
        elseif (size(self%items) /= capacity) then
            deallocate (self%items)
            allocate (self%items(capacity))
        end if

        self%log = 0

    end subroutine list_t_init

    !> Push item
    !> 推送值
    pure subroutine list_t_push(self, value)
        type(list_t), intent(inout) :: self     !! list
                                                !! 表
        integer, intent(in) :: value            !! value
                                                !! 值

        self%log = self%log + 1
        if (self%log > size(self%items)) then
            call self%expand()
        end if
        self%items(self%log) = value

    end subroutine list_t_push

    !> Merge list
    !> 合并列表
    pure subroutine list_t_merge(self, values)
        type(list_t), intent(inout) :: self     !! list
                                                !! 表
        type(list_t), intent(in) :: values      !! values
                                                !! 值

        do while (self%log + values%log > size(self%items))
            call self%expand()
        end do

        self%items(self%log + 1:self%log + values%log) = values%items(:values%log)
        self%log = self%log + values%log

    end subroutine list_t_merge

    !> Expand list size
    !> 拓展空间
    !> @note 空间低于 128 拓展到 128；高于 128，拓展到当前数组长度的 2 倍数
    pure subroutine list_t_expand(self)
        class(list_t), intent(inout) :: self    !! list
                                                !! 表
        integer :: n128

        n128 = size(self%items)/128
        if (n128 == 0) then
            self%items = expand_array(self%items, 128)
        else
            self%items = expand_array(self%items, 2*size(self%items))
        end if

    contains

        !> Expand array
        !> 拓展数组
        pure function expand_array(in, capacity) result(out)
            integer, intent(in) :: in(:)
            integer, intent(in) :: capacity
            integer, allocatable :: out(:)

            allocate (out(capacity))
            out(1:size(in)) = in

        end function expand_array

    end subroutine list_t_expand

end module list_type_m

!> Twin list structure
!> 孪生数组向量数据结构
!> @note 用于存储粒子对
module twin_list_type_m

    implicit none
    private

    public :: twin_list_t, twin_list_t_init, twin_list_t_push

    !> Twin list
    !> 孪生列表
    type twin_list_t
        integer, allocatable :: items(:, :)     !! list items
                                                !! 表元素
        integer :: log                          !! list length
                                                !! 表元素个数
    contains
        procedure, private :: expand => twin_list_t_expand
    end type twin_list_t

contains

    !> init length
    !> 初始化长度
    pure subroutine twin_list_t_init(self, capacity, save_capacity)
        type(twin_list_t), intent(inout) :: self    !! list
                                                    !! 表
        integer, intent(in) :: capacity             !! list capacity
                                                    !! 向量长度
        logical, intent(in) :: save_capacity        !! save capacity
                                                    !! 是否保存扩展后的长度

        if (.not. allocated(self%items)) then
            allocate (self%items(2, capacity))
        elseif (.not. save_capacity .and. size(self%items, 2) /= capacity) then
            deallocate (self%items)
            allocate (self%items(2, capacity))
        end if

        self%log = 0

    end subroutine twin_list_t_init

    !> Push item
    !> 推送值
    pure subroutine twin_list_t_push(self, values)
        type(twin_list_t), intent(inout) :: self    !! list
                                                    !! 表
        integer, intent(in) :: values(2)            !! values
                                                    !! 值

        self%log = self%log + 1
        if (self%log > size(self%items, 2)) then
            call self%expand()
        end if
        self%items(:, self%log) = values

    end subroutine twin_list_t_push

    !> Expand list size
    !> 拓展空间
    pure subroutine twin_list_t_expand(self)
        class(twin_list_t), intent(inout) :: self   !! list
                                                    !! 表

        self%items = expand_array(self%items, 2*size(self%items, 2))
    contains

        !> Expand array
        !> 拓展数组
        pure function expand_array(in, capacity) result(out)
            integer, intent(in) :: in(:, :)
            integer, intent(in) :: capacity
            integer, allocatable :: out(:, :)

            allocate (out(2, capacity))
            out(:, 1:size(in, 2)) = in

        end function expand_array

    end subroutine twin_list_t_expand

end module twin_list_type_m
